package com.wtgroup.demo.mianshi.算法.排序2305;
/*
 * # 冒泡排序
 * 
 * Tip: 大数往后冒, 小数自然往前冒了. 
 * 第一趟遍历, 最大数冒到最末尾, 
 * 第二趟, 第二大数冒到倒数第二位,
 * ...
 * 
 * 稳定
 */

public class BubbleSort {
	// 2017年9月24日 下午9:11:10  Nisus
	
	public static void main(String[] args) {
		
	}
	
	
	/* 冒泡排序 : 升序 */
	// int//
	public static void bubbleSort(int[] arr) {
		int len = arr.length;
		for (int i = len - 1; i > 0; i--) {
			for (int k = 0; k < i; k++) {
				if (arr[k] > arr[k + 1]) { // 最大的自然冒到后面去了
					int temp = arr[k];
					arr[k] = arr[k + 1];
					arr[k + 1] = temp;
				}

			}
		}
	}
	/* 冒泡排序 : 升序 --优化: 增加是否交换的标记 */
	// 某趟排序中, 如果没有发生交换, 那么就可以提前结束了
	// *: 经过测试, 数组随机程度较大时, 优化程度不明显
	// int//
	public static void bubbleSort2(int[] arr) {
		boolean is_swap = false;
		int len = arr.length;
		for (int i = len - 1; i > 0; i--) {
			for (int k = 0; k < i; k++) {
				if (arr[k] > arr[k + 1]) {
					int temp = arr[k];
					arr[k] = arr[k + 1];
					arr[k + 1] = temp;
					is_swap = true;  //发生了交换
				}

			}
			//没有发生交换表示前面都是正序了, 则返回.
			if (is_swap==false) {
				return;
			}
		}
	}
	
	/* 冒泡排序 : 升序 _局部_冒泡排序 */
	// 指定要排序的首末位置, 主要用于快速排序的优化上
	// int//
	public static void bubbleSort(int[] arr, int start, int end) {
		// int len = arr.length;
		for (int i = end; i > 0; i--) {
			for (int k = start; k < i; k++) {
				if (arr[k] > arr[k + 1]) {
					int temp = arr[k];
					arr[k] = arr[k + 1];
					arr[k + 1] = temp;
				}

			}
		}
	}

}
